/*
 * Copyright (c) 2022  by Junzhao
 * THIS FILE IS PART OF JAVA-Data-Structures-and-Algorithms PROJECT
 * All Rights Reserved.
 */

package 斐波那契;

import java.util.Arrays;

/**
 * @Description 斐波那契查找
 * 又叫黄金分割查找
 * 黄金分割点是指把一条线段分割为两部分，
 * 使其中一部分与全长之比等于另一部分与这部分之比。
 * 取其前三位数字的近似值是0.618。由于按此比例设计的造型十分美丽，
 * 因此称为黄金分割，也称为中外比。这是一个神奇的数字，会带来意向不大的效果。
 * <p>
 * 斐波那契数列 {1, 1, 2, 3, 5, 8, 13, 21, 34, 55 ...}
 * 发现斐波那契数列的两个相邻数 的比例，无限接近 黄金分割值0.618
 * <p>
 * 原理:
 * 斐波那契查找原理与前两种相似，仅仅改变了中间结点（mid）的位置，
 * mid不再是中间或插值得到，而是位于黄金分割点附近，
 * 即mid=low+F(k-1)-1（F代表斐波那契数列）
 * <p>
 * 对F(k-1)-1的理解：
 * 由斐波那契数列 F[k]=F[k-1]+F[k-2] 的性质，
 * 可以得到（F[k]-1）=（F[k-1]-1）+（F[k-2]-1）+1。该式说明：只要顺序表的长度为F[k]-1，
 * 则可以将该表分成长度为F[k-1]-1和F[k-2]-1的两段。从而中间位置为mid=low+F(k-1)-1
 * <p>
 * 类似的，每一子段也可以用相同的方式分割
 * 但顺序表长度n不一定刚好等于F[k]-1，所以需要将原来的顺序表长度n增加至F[k]-1。
 * 这里的k值只要能使得F[k]-1恰好大于或等于n即可，新增的位置（从n+1到F[k]-1位置），都赋为n位置的值即可。
 * @Author 俊昭
 * @Date 2022/5/2
 */
public class Fibonacci {
    public static int search(int[] arr, int num) {
        int[] f = Fib();
        int left = 0, right = arr.length - 1, mid;
        int k = 0;// 分割的数值下标

        //获取k
        while (right > f[k] - 1) {
            k++;
        }
        // 若得到的数列中的值大于了要查找的数列的长度 并用0填充
        int[] temp = Arrays.copyOf(arr, f[k]);
        // 线填充的0填充为原数组末尾值
        for (int i = right + 1; i < temp.length; i++) {
            temp[i] = arr[right];
        }
        while (left <= right) {
            mid = left + f[k - 1] - 1;
            if (temp[mid] == num) {
                return Math.min(mid, right);
                // <==> return (mid<=right)? mid:right;
            } else if (num < temp[mid]) {// 向左查找
                right = mid - 1;
                k--;
            } else if (num > temp[mid]) {// 向右查找
                left = mid + 1;
                k -= 2;
            }
        }
        return - 1;

    }

    private static int[] Fib() {
        int[] f = new int[20];
        f[0] = 1;
        f[1] = 1;
        for (int i = 2; i < 20; i++) {
            f[i] = f[i - 1] + f[i - 2];
        }

        return f;
    }
}
